package org.lql.algo.codecrush.hot100.binaryTree;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-09-07 18:31
 * @description: 124. 二叉树中的最大路径和 <a href="https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class MaxPathSum {

	private int maxSum = Integer.MIN_VALUE;

	public int maxPathSum(TreeNode root) {
		// 调用递归函数计算最大路径和
		maxGain(root);
		return maxSum;
	}

	private int maxGain(TreeNode node) {
		if (node == null) {
			return 0;
		}
		// 递归计算左右子节点的最大贡献值
		// 如果子树路径和为负，则不选取该子树（用0表示不选取）
		int leftGain = Math.max(maxGain(node.left), 0);
		int rightGain = Math.max(maxGain(node.right), 0);

		// 节点的最大路径和取决于该节点的值加上左右子节点的最大贡献值
		int currentMaxPath = node.val + leftGain + rightGain;

		// 更新全局最大路径和
		maxSum = Math.max(maxSum, currentMaxPath);

		// 返回节点的最大贡献值（只能选择一边）
		return node.val + Math.max(leftGain, rightGain);
	}
}
